HackerRank Common Child - 競プロ

HackerRank Common Child

https://www.hackerrank.com/challenges/common-child/problem

解答

code: python

import math

import os

import random

import re

import sys

#

# Complete the 'commonChild' function below.

#

# The function is expected to return an INTEGER.

# The function accepts following parameters:

# 1. STRING s1

# 2. STRING s2

#

def commonChild(s1, s2):

l_s1 = len(s1)

l_s2 = len(s2)

dp = [0 * (l_s1 + 1) for i in range(l_s2 + 1)]

for i in range(l_s1):

for j in range(l_s2):

if (s1i == s2j):

dpi + 1j + 1 = dpij + 1

else:

dpi + 1j + 1 = max(dpij + 1, dpi + 1j)

return dpl_s1l_s2

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

s1 = input()

s2 = input()

result = commonChild(s1, s2)

fptr.write(str(result) + '\n')

fptr.close()

テーマ

メモ

https://www.youtube.com/watch?v=ItRZRx8kvwY

https://scrapbox.io/files/61cfad0e255b500022d944cf.png

蟻本 2-3 最長共通部分列問題

文字列の類似度を計算する（LCS: 最長共通部分列）